// Terceiro trabalho de Programacao Concorrente
// Deteccao de Palavras
// Daniel Hatanaka, 7277579
// Guilherme Kalatzis, 7239426
// Thiago Tanaka, 7153014
// Prof. Dr. Julio Estrella, Estagiario PAE Luiz Henrique Nunes

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<omp.h>
#include<mpi.h>
//Define da nome do arquivo a ser utilizado
#define FILEPATH "palavras.txt"
//Define do numero de threads utilizadas no openMP
#define NTHREADS 8
//Numero maximo de palavras na tabela hash
#define MAX_HASH 4194301
//Numero maximo da palavra conforme solicitado no maximo 5 letras
#define MAXNLETTERS 5

//Vetor responsavel pela contagem do numero de palavras com 1 ,2 ,3 ,4 e 5 caracteres
//Eh utilizada para fazer o percentual de acerto de palavras por seu tamanho
int wordsWithNLetters[MAXNLETTERS + 1];

//Struct responsavel pelo armazenamento de informacoes do hashmap
typedef struct{
    char *word;
    int hs;
    int flag;
} HASH;

//Struct do hashtable
typedef struct{
    HASH *table;
    int qtdePalavras;
    int qtdePalavrasAchadas;
} HASH_ARQUIVO;


/* calcula o codigo hash */
int hash_code(char *key){
	//Declaracao de variaveis
    int i, hs_code = key[0];
    /* calcula o codigo hash lendo toda string */
    for (i = 1; key[i] != '\0'; i++){
    	//Calculo do hashcode utilizando um numero primo, no caso eh utilizado 251 e eh divido por outro primo no caso o MAX_HASH
      hs_code = (hs_code * 251 + key[i]) % MAX_HASH;
    }
    //Retorno do codigo hash calculado
    return hs_code;

}

/* insere palavra na tabela HASH */
int insert_ht(HASH_ARQUIVO **hsArquivo, char *word){
	//Recebe o hashcode da palavra
    int hs_code = hash_code(word);
    /* se a posicao da tabela estiver vazia eh inserido as palavras */
    if((*hsArquivo)->table[hs_code].hs != 1){
		//Alocacao dinamica da palavra
        (*hsArquivo)->table[hs_code].word = (char *)malloc(sizeof(char)*(strlen(word)+1));
        strcpy((*hsArquivo)->table[hs_code].word, word);
        //table[hs_code].word = aux;
        (*hsArquivo)->table[hs_code].hs = 1;
        (*hsArquivo)->qtdePalavras++;
        return 1;
    }
    /* se nao for vazia procura ate a proxima posicao vazia */
    else if((*hsArquivo)->table[hs_code].hs == 1){
        //Faz a comparacao para verificar se a palavra inserida e a mesma que esta no hashtable
        if(strcmp((*hsArquivo)->table[hs_code].word, word) == 0){
            return 0;
        }
        //Enquanto o hashtable estiver vazio ele faz a verificacao do proximo
        while((*hsArquivo)->table[hs_code].hs == 1){
            hs_code++;
        }
        //Alocacao dinamica da palavra
        (*hsArquivo)->table[hs_code].word = (char *)malloc(sizeof(char)*(strlen(word)+1));
        strcpy((*hsArquivo)->table[hs_code].word, word);
        (*hsArquivo)->table[hs_code].hs = 1;
        (*hsArquivo)->qtdePalavras++;
        return 1;
        }
	return 0;

}

/* remove uma palavra da tabela HASH */
//Funcao nao eh utilizada no projeto mas foi criada inicialmente
int remove_ht(HASH_ARQUIVO **hsArquivo, char *word){
	//Recebe o hashcode da palavra
    int hs_code = hash_code(word);
    /* se a palavra estiver na tabela eh removida*/
    if((*hsArquivo)->table[hs_code].hs != 0){
        /* se a posicao for a propria palavra remove */
        if((*hsArquivo)->table[hs_code].hs == 1 && strcmp(word, (*hsArquivo)->table[hs_code].word) == 0){
                char *aux;
                aux = (*hsArquivo)->table[hs_code].word;
                (*hsArquivo)->table[hs_code].word = NULL;
                free(aux);
                (*hsArquivo)->table[hs_code].hs = 2;
                (*hsArquivo)->qtdePalavras--;
                return 1;
        }
        /* se a posicao da tabela hash ja foi removida procura a proxima posicao para remover a palavra ou ate que ache um espaco vazio */
        while((*hsArquivo)->table[hs_code].hs == 2){
            hs_code++;
            if((*hsArquivo)->table[hs_code].hs == 1 && strcmp(word, (*hsArquivo)->table[hs_code].word) == 0){
                char *aux;
                aux = (*hsArquivo)->table[hs_code].word;
                (*hsArquivo)->table[hs_code].word = NULL;
                free(aux);
                (*hsArquivo)->table[hs_code].hs = 2;
                (*hsArquivo)->qtdePalavras--;
                return 1;
                }
            }
        }
    return 0;
}

/* procura uma palavra na tabela HASH */
int find_ht(HASH_ARQUIVO **hsArquivo, char *key){
    int hs_code = hash_code(key);
    /* se existe ou existiu a palavra, se existe verifica se a posicao eh a proxima palavra encontrada.. se existiu a palavra procura
    a proxima posicao ate encontrar uma posicao que existe alguma palavra... se a palavra for encontrada mostra na saida padrao retorna 1 , caso nao seja encontrada retorna 0 */
    if((*hsArquivo)->table[hs_code].hs != 0){
    	//Faz a comparacao se a palavra encontrada eh a que queremos
        if((*hsArquivo)->table[hs_code].hs == 1 && strcmp(key, (*hsArquivo)->table[hs_code].word) == 0 && (*hsArquivo)->table[hs_code].flag == 0){
            (*hsArquivo)->table[hs_code].flag = 1;
            (*hsArquivo)->qtdePalavrasAchadas++;
            return 1;

        }
        else if((*hsArquivo)->table[hs_code].hs == 2){
            while((*hsArquivo)->table[hs_code].hs == 2){
                hs_code++;
                if((*hsArquivo)->table[hs_code].hs == 1 && strcmp(key, (*hsArquivo)->table[hs_code].word) == 0 && (*hsArquivo)->table[hs_code].flag == 0){
                    (*hsArquivo)->table[hs_code].flag = 1;
                    (*hsArquivo)->qtdePalavrasAchadas++;
                    return 1;

                    }

                }

            }

        }
    return 0;

}

/* inicia o vetor HASH */
int init_vet(HASH_ARQUIVO **hsArquivo, int tam){
	//Inicia a alocacao da hashtable
    *hsArquivo = (HASH_ARQUIVO *)malloc(sizeof(HASH_ARQUIVO));
    //Seta os valores iniciais
    (*hsArquivo)->qtdePalavras = 0;
    (*hsArquivo)->qtdePalavrasAchadas = 0;
    (*hsArquivo)->table = (HASH *)malloc(sizeof(HASH)*tam);
    int i;
    for(i=0; i<tam; i++){
        (*hsArquivo)->table[i].hs = 0;
        (*hsArquivo)->table[i].word = NULL;
        (*hsArquivo)->table[i].flag = 0;
    }
    return 1;
}

/* desaloca os elementos do vetor HASH */
int desalloc_vet(HASH_ARQUIVO **hsArquivo, int tam){
    int i;
    char *aux;
    for(i=0; i<tam; i++){
    	//Seta os valores iniciais do hashtable
        if((*hsArquivo)->table[i].hs != 0){
            (*hsArquivo)->table[i].hs = 0;
            (*hsArquivo)->table[i].flag = 0;
            aux = (*hsArquivo)->table[i].word;
            free(aux);
            (*hsArquivo)->table[i].word = NULL;
        }
    }
    free((*hsArquivo)->table);
    free(hsArquivo);

    return 1;

}
//Rotina para gerar uma palavra aleatoria de acordo com o tamanho da palavra inserido
void newWord(char *word, int length) {
	int i, inteiro = 97, x, tamPalavra;
	char a;
	for (i = 0; i < length; i++){
		//Gera um valor aleatorio de 0 a 26
		x = rand() % 26;
		//Somamos 97 para encontra os caracteres da tabela ascii que ficam em lowercase
		x = inteiro + x;
		word[i] = x;
	}
	word[i] = '\0';
}

//Eh a rotina responsavel por encontrar a palavra dentro do arquivo palavras.txt e inserir no hash
void parseWords(char *buffer, HASH_ARQUIVO **hsArquivo) {
	int i, j, index = 0, bufferLength = strlen(buffer), success;
	char character, word[10000];

	// Percorre todos os caracteres da parte da entrada
	for (i = 0; i < bufferLength; i++) {
		character = buffer[i];
		if (character == ',' || character == ' ' || character == '-' || character == '\r') {
			// Finaliza a palavra pois achou marcador final de palavra
			word[index] = '\0';
			success = insert_ht(hsArquivo, word);
			if (success && strlen(word) <= MAXNLETTERS)
				wordsWithNLetters[strlen(word)]++;
			//if (strlen(word) > 0)
				//puts(word);
			// Verifica palindromo de palavra
			index = 0;
		}
		// A funcao strchr checa se existe a ocorrencia de um caractere em uma string - retorna o ponteiro da primeira ocorrencia
		// Logo, se o caractere nao esta contido na lista de ignorados, ele pode ser adicionado a palavra
		else {
			// Transforma as letras em minusculas
			if (character >= 'A' && character <= 'Z')
				character += 'a' - 'A';
			// Adiciona o caractere a palavra
			word[index++] = character;
		}
	}
	// O for terminara quando a entrada acabar, porem a ultima palavra tem que ser finalizada para nao ser perdida
	word[index] = '\0';
	//	insert_ht(hsArquivo, word);
	success = insert_ht(hsArquivo, word);
	if (success && strlen(word) <= MAXNLETTERS)
			wordsWithNLetters[strlen(word)]++;
	// Verifica palindromos
}

int main(int argc, char* argv[]){
	//Declaracao do hash
    HASH_ARQUIVO *teste;
    
    srand((unsigned)time(NULL));
    //Inicializacao do hash com seu tamanho
    init_vet(&teste, 4194304);
    double startingTime = 0, endingTime = 0, totalTime = 0, auxTime = 0;
    //Declaracao do arquivo
    FILE *file;
	int i, fileSize, index, previousIndex, j, verify, rank, size;
	char *fileBuffer;
	//Responsavel por receber o status do mpi
	MPI_Status status;
	//Inicializa o MPI
	verify = MPI_Init(&argc, &argv);
	//Comeca a contagem de tempo
	startingTime = MPI_Wtime();
	//Verifica se a inicializacao retorna sucesso ou nao
	if(verify != MPI_SUCCESS){
        printf("Erro...\n");
        exit(1);
    }
    // Salva em RANK o numero do processo criado
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    // Salva em SIZE o numero de processos a serem criados
    MPI_Comm_size(MPI_COMM_WORLD, &size);


	//Vetor responsavel pela porcentagem de palavras encontradas e nao encontradas
    int percentage[MAXNLETTERS + 1], found[MAXNLETTERS + 1];
	//Inicializa o vetor responsavel pela contagem de palavras com 0
	for (i = 1; i <= MAXNLETTERS; i++)
		wordsWithNLetters[i] = 0;
	
	//Responsavel por separar as partes do arquivo
    char *parts[size];

	// Atribui o numero de threads a ser utilizados com a OpenMP
	omp_set_num_threads(NTHREADS);
	//Se o rank eh o 0 ele eh o pai que vai fazer a comunicacao entre os nos.
    if(rank == 0){
    	//Abrimos o arquivo
        file = fopen(FILEPATH, "r");
        //Verificamos se ele abriu com sucesso
        if (file == NULL) {
            puts("Error reading file.");
        } else {
            // Move o cursor para o fim do arquivo
            fseek(file, 0, SEEK_END);
            // Descobre o tamanho do arquivo
            fileSize = ftell(file);
            // Volta o cursor para o comeco
            fseek(file, 0, SEEK_SET);
            // Aloca memoria para o buffer
            fileBuffer = (char *)calloc(sizeof(char), fileSize);
            // Le o arquivo inteiro e passa o conteudo para o vetor alocado
            fread(fileBuffer, sizeof(char), fileSize, file);

            previousIndex = 0;
            // Variavel para indicar tamanho da parte a ser enviada
            long tamEnvio=0;
            // Divide o conteudo do arquivo em varias partes (de acordo com o numero de processos a ser utilizado)
            for(i = 0; i < size-1; i++) {
                // Coloca um marcador na posicao final da parte a ser coletada
                index = (i + 1) * fileSize / (size-1);
				// Procura por um ponto ou espaco proximo, para palavras nao ficarem incompletas
				while (index != strlen(fileBuffer) && fileBuffer[index] != '.' && fileBuffer[index] != ' ')
					index++;
                // Aloca a memoria para a parte do arquivo de entrada
				parts[i] = (char *)calloc(sizeof(char), index - previousIndex);
				// Atualiza o tamanho da parte a ser enviada
				tamEnvio = index - previousIndex;
                // Copia o trecho do buffer para o vetor alocado
				strncpy(parts[i], fileBuffer + previousIndex, index - previousIndex);
				// Atualiza o marcador de comeco da parte
				previousIndex = index;
				// Envia o valor do tamanho da parte para cada processo
				MPI_Send(&tamEnvio, 1, MPI_LONG, i+1, 4, MPI_COMM_WORLD);
                // Envia a parte do arquivo para cada processo
				MPI_Send(parts[i], tamEnvio, MPI_CHAR, i+1, 1, MPI_COMM_WORLD);
			}
			// Desaloca as partes auxiliares que foram enviadas
			for (i = 0; i < size-1; i++){
                free(parts[i]);
            }
            //parseWords(fileBuffer, &teste);
            // Fecha arquivo e libera memoria
            fclose(file);
            free(fileBuffer);
        }

	}
	else{
        long tamEnvio=0;
		char *bloco;
        int auxWord=0, auxPrime=0;

        // Recebe o tamanho do bloco do arquivo a ser alocado
        MPI_Recv(&tamEnvio, 1, MPI_LONG, 0, 4, MPI_COMM_WORLD, &status);
        // Aloca o bloco para receber a parte do arquivo
        bloco = (char *)malloc(tamEnvio*sizeof(char));
        // Recebe a parte do arquivo a ser processada
        MPI_Recv(bloco, tamEnvio, MPI_CHAR, 0, 1, MPI_COMM_WORLD, &status);
		//Eh a rotina responsavel por encontrar a palavra dentro do arquivo palavras.txt e inserir no hash
        parseWords(bloco, &teste);
        //Responsavel pela porcentagem de palavras que encontraremos de cada tamanho de palavra
        for (i = 1; i <= MAXNLETTERS; i++) {
            percentage[i] = wordsWithNLetters[i] * 0.4;
            found[i] = 0;
        }
        char *word;
        for (j = 1; j <= MAXNLETTERS; j++) {
			//printf("Gerando palavras com %d letras.\n", j);
            word = (char *)malloc(sizeof(char) * (j + 1));
            //Paralelizacao do for utilizando openMP
            #pragma omp parallel for
            for (i = 1; i <= percentage[j]; i++) {
                newWord(word, j);
                #pragma omp critical
                //While responsavel por buscar se a palavra aleatoria criada esta ou nao no hash
                while (!find_ht(&teste, word)){
                	//Rotina para gerar uma palavra aleatoria de acordo com o tamanho da palavra inserido
                    newWord(word, j);
    				//printf("%s\n", word);
                }
                //Vetor responsavel por salvar o numero de palavras encontradas por tamanho de frase
                found[j]++;

                int k;

            }
        }



	}
	//Recebe o tempo final
	endingTime = MPI_Wtime();
	//Finaliza MPI
    MPI_Finalize();
	//Calcula o tempo total subtraindo o Final do Inicial
    totalTime = endingTime - startingTime;
    //Impressao da tempo total
    printf("%.2lfs\n", totalTime);





    return 0;
}
